Eulers sats

Eulers sats inom talteorin säger att för positiva heltal a och n sådana att a och n är relativt prima så gäller

$a^{\varphi (n)}\equiv 1\ (\operatorname {mod} \ n)$

där φ(n) betecknar Eulers φ-funktion.

Satsen är en generalisering av Fermats lilla sats.

En viktig tillämpning av satsen är vid RSA-kryptering, då man utnyttjar att det för heltal a och primtal p och q sådana att p ≠ q och SGD(a,p) = SGD(a,q) = 1 gäller att a^(p-1)(q-1) ≡ 1 (mod p⋅q), vilket följer av satsen eftersom Φ(p⋅q) = (p-1)(q-1), om p och q är olika primtal och SGD(a,pq) = 1.

Satsen kan användas för att lättare reducera stora potenser modulo n. Betrakta till exempel problemet att hitta den sista decimalsiffran av 7²²², dvs 7²²² (mod 10). Notera att 7 och 10 är relativt prima, och att φ(10) = 4. Eulers sats ger att 7⁴ = 1 (mod 10), och vi får 7²²² = 7^{4·55 + 2} = (7⁴)⁵⁵·7² = 1⁵⁵·7² = 49 = 9 (mod 10).

Generellt när man reducerar en potens av a modulo n (där a och n är relativt prima) måste man arbeta modulo φ(n) i exponenten till a. Detta är innebörden i en alternativ formulering av Eulers sats, nämligen att om a och n är relativt prima så gäller:

$x\equiv y\ (\operatorname {mod} \ \varphi (n))\Rightarrow a^{x}\equiv a^{y}\ (\operatorname {mod} \ n)$

Bevis

Leonhard Euler publicerade ett bevis 1736. Satsen kan bevisas genom att använda Lagranges teorem från den abstrakta algebran. Talen a som är relativt prima med n bildar en grupp under multiplikation mod n. Detta är enhetsgruppen till ringen Z/nZ. Denna grupp har φ(n) element, och Eulers sats följer sedan från Lagranges teorem.

Nedan följer ett bevis som utnyttjar det faktum att värdet av φ(m) är antalet inverterbara element i Z_m = {0, 1, 2, ..., m-1}.

Antag SGD(y,m) = 1. För y = z + r·m (där z,r ε Z_m) vill vi visa att SGD(z,m) = 1 och att y^φ(m) ≡ z^φ(m) (mod m), ty om SGD(z,m) = 1 är z^φ(m) ≡ 1(mod m), vilket skulle bevisa satsen.

z^φ(m) ≡ 1(mod m) om SGD(z,m) = 1

SGD(z,m) = 1 är ekvivalent med att z är inverterbar i Z_m. Ty om z är inverterbar finns ett tal c ε Z_m s.a. z·c ≡ 1 (mod m), så z·c - k·m = 1 för något k. En delare till z och m delar z·c och därmed även 1, så SGD(z,m) = 1. Omvänt gäller att om SGD(z,m) = 1 så existerar heltal z' och c' s.a. z·z' + c·c' = 1 (detta inses enklast genom att utföra euklides algoritm baklänges), dvs. z·z' ≡ 1 (mod m), så z är inverterbar.

Låt U_m = {x₁, x₂, ..., x_k} vara mängden av alla inverterbara element i Z_m och ansätt a,b ε U_m. Då är (a·b)⁻¹ = a⁻¹·b⁻¹ (detta gäller för godtyckliga a,b ε U_m). (a·b)·(a·b)⁻¹ = (a·b)·a⁻¹·b⁻¹ = a·(b·b⁻¹)·a⁻¹ ≡ a·a⁻¹ ≡ 1 (mod m), så a·U_m ⊆ U_m. Att b = 1·b ≡ a·a⁻¹·b = a·(a⁻¹·b) (mod m) medför att U_m ⊆ a·U_m vilket ger att a·U_m = U_m. Eftersom z är inverterbar följer att (z·x₁)·(z·x₂)·...·(z·x_k) ≡ x₁·x₂·...·x_k (mod m), så z^φ(m) ≡ 1 (mod m).

SGD(z,m) = 1 och y^φ(m) ≡ z^φ(m) (mod m)

En delare till z och m delar även y = z + r·m, så SGD(z,m) = 1 (Vi har ju antagit att SGD(y,m) = 1).

y^φ(m) = (z + r·m)^φ(m) = (enligt binomialsatsen) = $\sum _{i=0}^{\varphi (m)}{\binom {\varphi (m)}{i}}z^{i}\,(rm)^{\varphi (m)-i}=z^{\varphi (m)}+\sum _{i=0}^{\varphi (m)-1}{\binom {\varphi (m)}{i}}z^{i}\,(rm)^{\varphi (m)-i}\equiv z^{\varphi (m)}(\operatorname {mod} \ m)$

Det sista steget i beräkningarna följer av att φ(m) − i ≠ 0 för i ε [0, φ(m) − 1].

QED.

Se även

• Eulers formel